package exam.dfs;


import java.util.Scanner;

/**
 * HJ44
 * 数独
 *
 * index行列下标转换  row=count/9(行标) col=count%9 (列标)
 *
 *
 *
 * @author shenenlu 2021年04月29日 下午15:32:29
 */
public class Sudoku {

    private int[][] matrix;

    private boolean canFill;

    public Sudoku(int[][] panel) {
        this.matrix = panel;
        canFill = false;
    }


    /* 判断key填入n格时是否满足条件,n代表第几个格子 */
    boolean check(int n, int key)
    {
        /* 判断n所在横列是否合法 */
        for (int i = 0; i < 9; i++){
            /* j为n竖坐标 */
            int j = n / 9;
            if (matrix[j][i] == key)
                return false;
        }

        /* 判断n所在竖列是否合法 */
        for (int i = 0; i < 9; i++){
            /* j为n横坐标 */
            int j = n % 9;
            if (matrix[i][j] == key)
                return false;
        }

        int y = n / 9 / 3 * 3;
        int x = n % 9 / 3 * 3;
        /* 判断n所在的小九宫格是否合法 */
        for (int i = y; i < y + 3; i++)
            for (int j = x; j < x + 3; j++)
                if (matrix[i][j] == key)
                    return false;

        return true;
    }

    /* 深搜 */
    void dfs(int n)
    {
        /* 所有的都符合，退出搜索,n代表格子数，共81个格子，0~80 */
        if (n >= 81){
            canFill = true;
            return;
        }

        if (matrix[n / 9][n % 9] != 0)
            dfs(n + 1);
        else{
            /* 否则对当前位一次填入1~9进行测试 */
            for (int i = 1; i <= 9; i++){
                if (check(n, i)){
                    matrix[n / 9][n % 9] = i;
                    /* 继续搜索，后续位也填1~9测试，直到最后一位，通过的话置true */
                    dfs(n + 1);
                    /* 返回时如果构造成功，则直接退出 */
                    if (canFill)
                        return;
                    /* 如果构造不成功，还原当前位 */
                    matrix[n/9][n%9] = 0;
                }
            }
        }
    }


    public static void main(String[] args) {
        int[][] matrix = new int[9][9];
        Scanner scanner = new Scanner(System.in);
        for(int i = 0; i < 9; i++){
            String[] lineStrArr = scanner.nextLine().split(" ");
            if( lineStrArr.length != 9){
                throw new IllegalArgumentException();
            }
            for( int j = 0; j< 9; j++){
                matrix[i][j] = Integer.parseInt(lineStrArr[j]);
            }
        }

        Sudoku sudoku = new Sudoku(matrix);
        sudoku.dfs(0);
        for( int[] matrixLine : matrix ){
            for( int value : matrixLine){
                System.out.print(value + " ");
            }
            System.out.println();
        }
    }

}
